<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    380. Insert Delete GetRandom O(1)
   </h1>
   <p>
    Design a data structure that supports all following operations in
    <i>
     average
    </i>
    <b>
     O(1)
    </b>
    time.
   </p>
   <p>
   </p>
   <ol>
    <li>
     <code>
      insert(val)
     </code>
     : Inserts an item val to the set if not already present.
    </li>
    <li>
     <code>
      remove(val)
     </code>
     : Removes an item val from the set if present.
    </li>
    <li>
     <code>
      getRandom
     </code>
     : Returns a random element from current set of elements. Each element must have the
     <b>
      same probability
     </b>
     of being returned.
    </li>
   </ol>
   <p>
    <b>
     Example:
    </b>
   </p>
   <pre>
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();
</pre>
  </div>
  <div>
   <h1 class="question_title">
    380. 常数时间插入、删除和获取随机元素
   </h1>
   <p>
    设计一个支持在
    <em>
     平均&nbsp;
    </em>
    时间复杂度
    <strong>
     O(1)
    </strong>
    &nbsp;下，执行以下操作的数据结构。
   </p>
   <ol>
    <li>
     <code>
      insert(val)
     </code>
     ：当元素 val 不存在时，向集合中插入该项。
    </li>
    <li>
     <code>
      remove(val)
     </code>
     ：元素 val 存在时，从集合中移除该项。
    </li>
    <li>
     <code>
      getRandom
     </code>
     ：随机返回现有集合中的一项。每个元素应该有
     <strong>
      相同的概率
     </strong>
     被返回。
    </li>
   </ol>
   <p>
    <strong>
     示例 :
    </strong>
   </p>
   <pre>
// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();
</pre>
  </div>
 </body>
</html>